//
//  ReversiBoard.m
//  Reversi
//
//  Created by 成瀬 龍人 on 2/4/10.
//  Copyright 2010 __MyCompanyName__. All rights reserved.
//

#import "ReversiBoard.h"

@implementation ReversiBoard
+ (int)countBitNum:(uint64)target{
	target = ((target >> 1) &  0x5555555555555555) + (target & 0x5555555555555555);
	target = ((target >> 2) &  0x3333333333333333) + (target & 0x3333333333333333);
	target = ((target >> 4) &  0x0f0f0f0f0f0f0f0f) + (target & 0x0f0f0f0f0f0f0f0f);
	target = ((target >> 8) &  0x00ff00ff00ff00ff) + (target & 0x00ff00ff00ff00ff);
	target = ((target >> 16) & 0x0000ffff0000ffff) + (target & 0x0000ffff0000ffff);
	target =  (target >> 32)                       + (target & 0x00000000ffffffff);
	return target;
}

- (id)init{
	[super init];
	black = 0;
	white = 0;
	return self;
}

- (id)initForGame{
	[self init];
	black = 0;
	white = 0;
	black |= int2mask(4,4);
	black |= int2mask(5,5);
	white |= int2mask(5,4);
	white |= int2mask(4,5);
	return self;
}

- (id)initWithString:(NSString*)board{
	[super init];
	black = (uint64)0;
	white = (uint64)0;
	for(int i = 0; i < [board length]; ++i){
		if ([board characterAtIndex:i] == '@'){
			black = black | index2mask(i + 1);
		}else if([board characterAtIndex:i] == 'O'){
			white = white | index2mask(i + 1);
		}
	}
	return self;
}

- (void)put:(ReversiStone)stone mask:(uint64)mask{
	uint64* target = (stone == REVERSI_STONE_BLACK) ? &black : &white;
	uint64* not_target = (stone == REVERSI_STONE_BLACK) ? &white : &black;
	*target = (*target) | mask;
	*not_target = (*not_target) & (~mask);	
}

- (void)put:(ReversiStone)stone:(ReversiBoardPosition*)pos{
	uint64 mask = pos2mask(pos);
	[self put:stone mask:mask];
}

- (void)clearWithMask:(uint64)mask{
	black = black & ~mask;
	white = white & ~mask;
}

- (void)clear:(ReversiBoardPosition*)pos{
	uint64 mask = pos2mask(pos);
	[self clearWithMask:mask];
}

- (void)allClear{
	black = 0;
	white = 0;
}

- (bool)is:(ReversiStone)stone mask:(uint64)mask{
	uint64 target = (stone == REVERSI_STONE_BLACK) ? black : white;
	return (target & mask) != 0;
}

- (bool)is:(ReversiStone)stone:(ReversiBoardPosition*)pos{
	uint64 mask = pos2mask(pos);
	return [self is:stone mask:mask];
}

- (bool)isFreeWithMask:(uint64)mask{
	return ((black | white) & mask) == 0;
}

- (bool)isFree:(ReversiBoardPosition*)pos{
	uint64 mask = pos2mask(pos);
	return [self isFreeWithMask:mask];
}

- (bool)isFull{
	return (~(black | white)) == 0;
}

- (bool)isGameOver{
	if ([self isFull]){
		return true;
	}
	if ([[self allocatablePositions:REVERSI_STONE_BLACK] count] == 0 && 
		[[self allocatablePositions:REVERSI_STONE_WHITE] count] == 0){
		return true;
	}
	return false;
	
}

- (NSArray*)allocatablePositions:(ReversiStone)stone{
	NSMutableArray* array = [[NSMutableArray alloc] init];
	for (int y = 1; y <= 8; ++y ){
		for (int x = 1; x <= 8; ++x){
			uint64 mask = int2mask(x, y);
			if ([self isPutOK:stone mask:mask]){
				[array addObject:[[ReversiBoardPosition alloc] initWithInt:x:y]];
			}
		}
	}
	return array;
}

- (int)allocatablePositionsNum:(ReversiStone)stone{
	int num = 0;
	for (int y = 1; y <= 8; ++y ){
		for (int x = 1; x <= 8; ++x){
			uint64 mask = int2mask(x, y);
			if ([self isPutOK:stone mask:mask]){
				++num;
			}
		}
	}
	return num;
}

- (int)numberOf:(ReversiStone)stone{
	uint64 target = (stone == REVERSI_STONE_BLACK) ? black : white;
	return [[self class] countBitNum:target];
}
 
- (int)numberOfFree{
	uint64 target = ~(black | white);
	return [[self class] countBitNum:target];
}

- (void)invert{
	uint64 tmp = black;
	black = white;
	white = tmp;
}

- (NSString*)description{
	NSMutableString* str = [[NSMutableString alloc] init];
	for(int y = 1; y <= 8; ++y){
		for(int x = 1; x <= 8; ++x){
			uint64 mask = int2mask(x,y);
			if ((black & mask) != 0){
				[str appendString:@"@"];
			}else if ((white & mask) != 0){
				[str appendString:@"O"];
			}else {
				[str appendString:@"+"];
			}
		}
		[str appendString:@"\n"];
	}
	return str;
}

- (bool)isEqual:(id)object{
	if ([object isKindOfClass:[self class]]){
		return	white == ((ReversiBoard*)object)->white &&
				black == ((ReversiBoard*)object)->black;
	}
	return false;
}

- (id)copyWithZone:(NSZone*)zone{
	ReversiBoard* obj = [[[self class] alloc] init];
	obj->black = black;
	obj->white = white;
	return obj;
}

- (bool)isPutOK:(ReversiStone)stone mask:(uint64)aMask{
	uint64 self_board = (stone == REVERSI_STONE_BLACK) ? black : white;
	uint64 other_board = (stone == REVERSI_STONE_BLACK) ? white : black;
	
	//石が置かれていないか
	if (((self_board | other_board) & aMask) != 0){
		return false;
	}
	
	//上
	uint64 mask = transferU(aMask);
	bool ret = false;
	while (mask != 0 && (other_board & mask) != 0){
		ret = true;
		mask = transferU(mask);
	}
	if ((self_board & mask) != 0 && ret){
		return ret;
	}
	
	//右上
	mask = transferUR(aMask);
	ret = false;
	while (mask != 0 && (other_board & mask) != 0){
		ret = true;
		mask = transferUR(mask);
	}
	if ((self_board & mask) != 0 && ret){
		return ret;
	}
	
	//右
	mask = transferR(aMask);
	ret = false;
	while (mask != 0 && (other_board & mask) != 0){
		ret = true;
		mask = transferR(mask);
	}
	if ((self_board & mask) != 0 && ret){
		return ret;
	}
	
	//右下
	mask = transferDR(aMask);
	ret = false;
	while (mask != 0 && (other_board & mask) != 0){
		ret = true;
		mask = transferDR(mask);
	}
	if ((self_board & mask) != 0 && ret){
		return ret;
	}
	
	//下
	mask = transferD(aMask);
	ret = false;
	while (mask != 0 && (other_board & mask) != 0){
		ret = true;
		mask = transferD(mask);
	}
	if ((self_board & mask) != 0 && ret){
		return ret;
	}
	
	//左下
	mask = transferDL(aMask);
	ret = false;
	while (mask != 0 && (other_board & mask) != 0){
		ret = true;
		mask = transferDL(mask);
	}
	if ((self_board & mask) != 0 && ret){
		return ret;
	}
	
	//左
	mask = transferL(aMask);
	ret = false;
	while (mask != 0 && (other_board & mask) != 0){
		ret = true;
		mask = transferL(mask);
	}
	if ((self_board & mask) != 0 && ret){
		return ret;
	}
	
	//左上
	mask = transferUL(aMask);
	ret = false;
	while (mask != 0 && (other_board & mask) != 0){
		ret = true;
		mask = transferUL(mask);
	}
	if ((self_board & mask) != 0 && ret){
		return ret;
	}
	
	return false;
}

- (bool)isPutOK:(ReversiStone)stone:(ReversiBoardPosition*)pos{
	uint64 mask = pos2mask(pos);
	return [self isPutOK:stone mask:mask];
}

- (uint64)putAndChange:(ReversiStone)stone mask:(uint64)aMask{
	uint64 self_board = (stone == REVERSI_STONE_BLACK) ? black : white;
	uint64 other_board = (stone == REVERSI_STONE_BLACK) ? white : black;
	uint64* self_target = (stone == REVERSI_STONE_BLACK) ? &black : &white;
	uint64* other_target = (stone == REVERSI_STONE_BLACK) ? &white : &black;
	uint64 result_mask = 0;
	
	//石が置かれていないか
	if (((self_board | other_board) & aMask) != 0){
		return result_mask;
	}
	
	//上
	uint64 mask = transferU(aMask);
	uint64 tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferU(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//右上
	mask = transferUR(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferUR(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//右
	mask = transferR(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferR(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//右下
	mask = transferDR(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferDR(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//下
	mask = transferD(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferD(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//左下
	mask = transferDL(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferDL(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//左
	mask = transferL(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferL(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//左上
	mask = transferUL(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferUL(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//結果をボードに反映
	[self put:stone mask:aMask];
	*self_target  |= result_mask;
	*other_target &= ~result_mask;
	return result_mask;
}

- (void)putAndChange:(ReversiStone)stone:(ReversiBoardPosition*)pos{
	uint64 mask = pos2mask(pos);
	[self putAndChange:stone mask:mask];
}

- (NSArray*)putAndChangeEx:(ReversiStone)stone mask:(uint64)aMask pos:(ReversiBoardPosition*)pos{
	NSMutableArray* result_array = [[NSMutableArray alloc] init];	
	uint64 result_mask = 0;
	uint64 self_board = (stone == REVERSI_STONE_BLACK) ? black : white;
	uint64 other_board = (stone == REVERSI_STONE_BLACK) ? white : black;
	uint64* self_target = (stone == REVERSI_STONE_BLACK) ? &black : &white;
	uint64* other_target = (stone == REVERSI_STONE_BLACK) ? &white : &black;
	
	//石が置かれていないか
	if (((self_board | other_board) & aMask) != 0){
		return result_array;
	}
	
	//上
	uint64 mask = transferU(aMask);
	uint64 tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferU(mask);
	}
	if ((self_board & mask) != 0 && tmp_result_mask != 0){
		int num = [[self class] countBitNum:tmp_result_mask];
		[result_array addObject:[[ReversiBoardLineRange alloc] init:[[ReversiBoardPosition alloc] initWithInt:pos.x:pos.y-1]
																dir:[[ReversiBoardLineDirection alloc] init:0:-1]
																num:num]];
		result_mask |= tmp_result_mask;
	}
	
	//右上
	mask = transferUR(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferUR(mask);
	}
	if ((self_board & mask) != 0 && tmp_result_mask != 0){
		int num = [[self class] countBitNum:tmp_result_mask];
		[result_array addObject:[[ReversiBoardLineRange alloc] init:[[ReversiBoardPosition alloc] initWithInt:pos.x+1:pos.y-1]
																dir:[[ReversiBoardLineDirection alloc] init:1:-1]
																num:num]];
		result_mask |= tmp_result_mask;
	}
	
	//右
	mask = transferR(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferR(mask);
	}
	if ((self_board & mask) != 0 && tmp_result_mask != 0){
		int num = [[self class] countBitNum:tmp_result_mask];
		[result_array addObject:[[ReversiBoardLineRange alloc] init:[[ReversiBoardPosition alloc] initWithInt:pos.x+1:pos.y]
																dir:[[ReversiBoardLineDirection alloc] init:1:0]
																num:num]];
		result_mask |= tmp_result_mask;
	}
	
	//右下
	mask = transferDR(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferDR(mask);
	}
	if ((self_board & mask) != 0 && tmp_result_mask != 0){
		int num = [[self class] countBitNum:tmp_result_mask];
		[result_array addObject:[[ReversiBoardLineRange alloc] init:[[ReversiBoardPosition alloc] initWithInt:pos.x+1:pos.y+1]
																dir:[[ReversiBoardLineDirection alloc] init:1:1]
																num:num]];
		result_mask |= tmp_result_mask;
	}
	
	//下
	mask = transferD(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferD(mask);
	}
	if ((self_board & mask) != 0 && tmp_result_mask != 0){
		int num = [[self class] countBitNum:tmp_result_mask];
		[result_array addObject:[[ReversiBoardLineRange alloc] init:[[ReversiBoardPosition alloc] initWithInt:pos.x:pos.y+1]
																dir:[[ReversiBoardLineDirection alloc] init:0:+1]
																num:num]];
		result_mask |= tmp_result_mask;
	}
	
	//左下
	mask = transferDL(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferDL(mask);
	}
	if ((self_board & mask) != 0 && tmp_result_mask != 0){
		int num = [[self class] countBitNum:tmp_result_mask];
		[result_array addObject:[[ReversiBoardLineRange alloc] init:[[ReversiBoardPosition alloc] initWithInt:pos.x-1:pos.y+1]
																dir:[[ReversiBoardLineDirection alloc] init:-1:+1]
																num:num]];
		result_mask |= tmp_result_mask;
	}
	
	//左
	mask = transferL(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferL(mask);
	}
	if ((self_board & mask) != 0 && tmp_result_mask != 0){
		int num = [[self class] countBitNum:tmp_result_mask];
		[result_array addObject:[[ReversiBoardLineRange alloc] init:[[ReversiBoardPosition alloc] initWithInt:pos.x-1:pos.y]
																dir:[[ReversiBoardLineDirection alloc] init:-1:0]
																num:num]];
		result_mask |= tmp_result_mask;
	}
	
	//左上
	mask = transferUL(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferUL(mask);
	}
	if ((self_board & mask) != 0 && tmp_result_mask != 0){
		int num = [[self class] countBitNum:tmp_result_mask];
		[result_array addObject:[[ReversiBoardLineRange alloc] init:[[ReversiBoardPosition alloc] initWithInt:pos.x-1:pos.y-1]
																dir:[[ReversiBoardLineDirection alloc] init:-1:-1]
																num:num]];
		result_mask |= tmp_result_mask;
	}
	
	//結果をボードに反映
	[self put:stone mask:aMask];
	*self_target  |= result_mask;
	*other_target &= ~result_mask;
	return result_array;
}

- (NSArray*)putAndChangeEx:(ReversiStone)stone:(ReversiBoardPosition*)pos{
	uint64 mask = pos2mask(pos);
	return [self putAndChangeEx:stone mask:mask pos:pos];
}


- (int)numberOfWillChange:(ReversiStone)stone mask:(uint64)aMask{
	uint64 self_board = (stone == REVERSI_STONE_BLACK) ? black : white;
	uint64 other_board = (stone == REVERSI_STONE_BLACK) ? white : black;
	uint64 result_mask = 0;
	
	//石が置かれていないか
	if (((self_board | other_board) & aMask) != 0){
		return result_mask;
	}
	
	//上
	uint64 mask = transferU(aMask);
	uint64 tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferU(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//右上
	mask = transferUR(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferUR(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//右
	mask = transferR(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferR(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//右下
	mask = transferDR(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferDR(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//下
	mask = transferD(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferD(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//左下
	mask = transferDL(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferDL(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//左
	mask = transferL(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferL(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//左上
	mask = transferUL(aMask);
	tmp_result_mask = 0;
	while (mask != 0 && (other_board & mask) != 0){
		tmp_result_mask |= mask;
		mask = transferUL(mask);
	}
	if ((self_board & mask) != 0){
		result_mask |= tmp_result_mask;
	}
	
	//結果をボードに反映
	return [[self class] countBitNum:result_mask];
}

- (int)numberOfWillChange:(ReversiStone)stone:(ReversiBoardPosition*)pos{
	uint64 mask = pos2mask(pos);
	return [self numberOfWillChange:stone mask:mask];
}
@end
